package leetcode.pre100;


import java.util.LinkedList;
import java.util.List;

/**
 * 输出N皇后的所有解
 * 输入: 4
 * 输出: [
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 * <p>
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/n-queens
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code52_Nqueen4 {


    public static List<List<String>> printNqueen(int n) {
        if (n <= 0) {
            return new LinkedList<>();
        }
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = i;
        }
        List<List<String>> res = new LinkedList<>();
        process(array, 0,res);
        return res;
    }

    private static void process(int[] array, int index, List<List<String>> res) {

        //所有的都通过了，加1并打印
        if (index == array.length) {
            //处理array，按照要求格式输出
//            print(array);
            doProcess(array,res);
            return;
        }
        //全排列
        for (int i = index; i < array.length; i++) {
            swap(array, i, index);
            //因为当前的行和列一定满足条件，判断当前对角线是否满足，是的话则继续，否则放弃
            if (check(array, index)) {
                process(array, index + 1, res);
            }
            swap(array, index, i);
        }
    }

    private static void doProcess(int[] array, List<List<String>> res) {

        /**
         *  [".Q..",  // 解法 1
         *   "...Q",
         *   "Q...",
         *   "..Q."],
         *   arr = [1,3,0,2]
         */
        StringBuilder sb;
        List<String> list = new LinkedList<>();
        for (int i = 0; i < array.length; i++) {
            sb  = new StringBuilder();
            // arr[i]表示在第i列
            for (int j = 0; j < array.length; j++) {
                if(j == array[i]){
                    sb.append("Q");
                }else {
                    sb.append(".");
                }
            }
            list.add(sb.toString());
        }
        res.add(list);
    }

    //判断是否在同一对角线上，是的话，不满足条件
    private static boolean check(int[] array, int index) {

        //前0-index-2肯定不在对角线上了，所以只要判断index-1和 0-index-2是否在对角线上即可
        for (int i = 0; i < index; i++) {
            if (Math.abs(index - i) == Math.abs(array[index] - array[i])) {
                return false;
            }
        }
        return true;
    }


    private static void swap(int[] array, int i, int j) {
        if (i != j) {
            array[i] = array[i] ^ array[j];
            array[j] = array[i] ^ array[j];
            array[i] = array[i] ^ array[j];
        }
    }

    //打印皇后摆法数量
    private static void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + 1 + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {

        List<List<String>> lists = printNqueen(4);
        lists.forEach(System.out::println);
    }

}
